import java.util.Arrays;
import java.util.PriorityQueue;

public class Test {
    //找出数组中k个最大的数
    public static int[] maxK(int[] array, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        for (int i = 0; i < k; i++) {
            minHeap.offer(array[i]);
        }

        for (int i = k; i < array.length; i++) {
            int top = minHeap.peek();
            if (top < array[i]) {
                minHeap.poll();
                minHeap.offer(array[i]);
            }
        }

        int[] ret = new int[k];
        for (int i = 0; i < k; i++) {
            ret[i] = minHeap.poll();
        }
        return ret;
    }

    public static void main3(String[] args) {
        int[] array = {21, 55, 18, 67, 25};
        int[] ret = maxK(array, 3);
        System.out.println(Arrays.toString(ret));
    }

    //找出数组中k个最小的数
    public int[] smallestK(int[] array, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        //向上调整的方式建堆，时间复杂度为O(n * logN)
        for (int i = 0; i < array.length; i++) {
            minHeap.offer(array[i]);
        }

        int[] ret = new int[k];
        for (int i = 0; i < k; i++) {
            ret[i] = minHeap.poll();
        }
        return ret;
    }

    public static void main2(String[] args) {
        //默认是一个小根堆
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        priorityQueue.offer(1);
        priorityQueue.offer(3);
        priorityQueue.offer(4);
        priorityQueue.offer(7);

        System.out.println(priorityQueue.peek());
    }

    public static void main(String[] args) {
        TestHeap testHeap = new TestHeap();
        int[] array = {27, 15, 19, 18, 28, 34, 65, 49, 25, 37};
        testHeap.initElem(array);

        testHeap.createHeap();

        //testHeap.offer(80);
        //testHeap.poll();

        testHeap.heapSort();
    }
}
